package chapter03;

import chapter02.IsSameTree100;

public class IsSymmetric101 {
    /**
     * 深度优先遍历
     * 与100题思路差不多 区别在于本题是判断左右子树是否关于根节点对称 初始化将左右子树传入process
     * process(xNode,yNode) 以xNode和yNode为头的两颗树是否对称
     * 递归出口
     *  1).xNode==null&&yNode==null
     *      return true
     *  2).xNode==null&&yNode!=null||xNode!=null&&yNode==null||xNode.val!=yNode.val
     *      return false
     *  3).判断左 右子树是否对称
     *      x左子树对于y右子树 x右子树对于y左子树
     *      return process(xNode.left,yNode.right)&&process(xNode.right,yNode.left)
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return process(root.left,root.right);
    }

    public boolean process(TreeNode x,TreeNode y){
        if(x==null&&y==null){
            return true;
        }else if(x==null&&y!=null||x!=null&&y==null||x.val!=y.val){
            return false;
        }else{
            return process(x.left,y.right)&&process(x.right,y.left);
        }
    }
}
